package com.lun.swordtowardoffer2.c03;

import java.util.HashMap;

public class MinWindow {
	
	public String minWindow(String s, String t) {
		HashMap<Character, Integer> char2Count = new HashMap<>();
		
		for(char ch : t.toCharArray()) {
			char2Count.put(ch, char2Count.getOrDefault(ch, 0) + 1);
		}
		
		int count = char2Count.size();//字符串的字符总类数
		int start = 0, end = 0, minStart = 0, minEnd = 0;//子字符串的起始下标
		int minLength = Integer.MAX_VALUE;
		
		
		while(end < s.length() || (count == 0 && end == s.length())/*第2指针到最后也要执行一次循环体*/) {
			if(count > 0) {
				char endCh = s.charAt(end);
				if(char2Count.containsKey(endCh)) {
					char2Count.put(endCh, char2Count.get(endCh) - 1);
					if(char2Count.get(endCh) == 0)
						count--;
				}
				end++;
			}else {
				if(end - start < minLength) {
					minLength = end - start;
					minStart = start;
					minEnd = end;
				}
				char startCh = s.charAt(start);
				if(char2Count.containsKey(startCh)) {
					char2Count.put(startCh, char2Count.get(startCh) + 1);
					if(char2Count.get(startCh) == 1)
						count++;
				}
				start++;
			}
		}
		
		return minLength < Integer.MAX_VALUE ? s.substring(minStart, minEnd): "";
	}
	
}
